/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LIUYANJIAO
 * Date: 2024-10-28
 * Time: 14:30
 */
public class Main {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||root==p||root==q) return root;
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        if(left==null&&right==null) return null;
        if(left==null) return right;
        if(right==null) return left;
        return root;
    }
    public static boolean lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return false;
        if(root==p||root==q) {
            ans=root;
            return true;
        }
        return lowestCommonAncestor1(root.left,p,q)||
        lowestCommonAncestor1(root.right,p,q);
    }

    static TreeNode ans;
        public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root==p||root==q) return root;
            boolean b1=lowestCommonAncestor1(root.left,p,q);
            boolean b2=lowestCommonAncestor1(root.right,p,q);
            if(b1&&b2){
                ans=root;
            }
            return ans;
        }

        public static void main(String[] args) {
            TreeNode a=new TreeNode(-1);
            TreeNode b=new TreeNode(0);
            TreeNode c=new TreeNode(3);
            TreeNode d=new TreeNode(-2);
            TreeNode e=new TreeNode(4);
            TreeNode f=new TreeNode(8);
            a.left=b;
            a.right=c;
            b.left=d;
            b.right=e;
            d.left=f;
            lowestCommonAncestor(a,d,f);

        }
    }
